package class07


/*
	题目一
		给定一个无序数组arr,如果只能在一个子数组上排序
		返回如果让arr整体有序，需要排序的最短子数组长度

	例子：	1 2 5 3 2 4 6 7
			0 1 2 3 4 5 6 7
		此时：5 3 2 4 的子数组无需，在这个子数组上排序，整体则有序。子数组的最短长度为4

	算法流程：
		时间复杂度O(N),额外空间复杂度O(1)
		1. 确定右侧不用排序的位置
			从左向右遍历，记录左侧最大值
			max左 | i
			到i位置时，判断 i >= max左
				如果符合，打对号
				如果不符合，打叉号，直到遍历完，记录最后的叉号

		2. 确定左侧不用排序的位置
			从右向左遍历，记录右侧最小值
			 i | min右
			到i位置时，判断 i <= min右
				如果符合，打对号
				如果不符合，打叉号，直到遍历完，记录最后的叉号位置

		3. 计算出需要排序的区间。
*/
func GetMinLength(arr []int) int {
	if len(arr) < 2 {
		return 0
	}
	noSuitRight, noSuitLeft := -1, -1
	leftMax := arr[0]
	for i:=1; i<len(arr); i++ {
		if arr[i] < leftMax {
			noSuitRight = i
		} else {
			leftMax = arr[i]
		}
	}
	// 有序数组的情况，直接返回0长度
	if noSuitRight == -1 {
		return 0
	}
	rightMin := arr[len(arr)-1]
	for i:=len(arr)-2; i>=0; i-- {
		if arr[i] > rightMin {
			noSuitLeft = i
		} else {
			rightMin = arr[i]
		}
	}
	return noSuitRight-noSuitLeft+1
}
